package leetcode;

import java.util.*;

/**
 * Created by lingfengsan on 2018/9/28.
 *
 * @author lingfengsan
 */
// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }

    public static TreeNode buildTree(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(nums[0]);
        queue.offer(root);
        for (int i = 0; i < nums.length; ) {
            Queue<TreeNode> temp = new LinkedList<>();
            while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                if (++i < nums.length && nums[i] != -1) {
                    cur.left = new TreeNode(nums[i]);
                    temp.offer(cur.left);
                }
                if (++i < nums.length && nums[i] != -1) {
                    cur.right = new TreeNode(nums[i]);
                    temp.offer(cur.right);
                }
            }
            queue = temp;
        }
        return root;
    }


    public static void prePrint(TreeNode node) {
        if (node == null) return;
        System.out.print(node.val + ",");
        if (node.left != null) prePrint(node.left);
        if (node.right != null) prePrint(node.right);
    }


}

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.filterString("test.email+alex@leetcode.com"));
    }

    public int numUniqueEmails(String[] emails) {
        TreeSet<String> ts = new TreeSet<>();
        for (String email : emails) {
            ts.add(filterString(email));
        }
        return ts.size();
    }

    private String filterString(String str) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == '+' || c == '@') break;
            if (c != '.')
                sb.append(c);
        }
        sb.append(str, str.indexOf('@'), str.length());
        return sb.toString();
    }

    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) return null;
        if (root.val < L || root.val > R) {
            if (root.val < L && root.val > R) return null;
            if (root.val < L) {
                return trimBST(root.right, L, R);
            } else {
                return trimBST(root.left, L, R);
            }
        } else {
            root.left = trimBST(root.left, L, R);
            root.right = trimBST(root.right, L, R);
        }
        return root;
    }

    public int[][] matrixReshape(int[][] nums, int r, int c) {
        if (nums.length * nums[0].length != r * c) return nums;
        int[][] ans = new int[r][c];
        int x = 0, y = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[0].length; j++) {
                if (y >= c) {
                    x++;
                    y = 0;
                }
                ans[x][y++] = nums[i][j];
            }
        }
        return ans;
    }

    public List<String> fizzBuzz(int n) {
        List<String> list = new ArrayList<>(n);
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0) {
                if (i % 5 == 0) {
                    list.add("FizzBuzz");
                } else {
                    list.add("Fizz");
                }
            } else if (i % 5 == 0) {
                list.add("Buzz");
            } else {
                list.add(i + "");
            }
        }
        return list;
    }

    public int findLUSlength(String a, String b) {
        if (a == null && b == null) return -1;
        if (a == null) return b.length();
        if (b == null) return a.length();
        if (a.length() != b.length()) return Math.max(a.length(), b.length());
        if (a.equals(b)) return -1;
        return a.length();
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBSTHelper(nums, 0, nums.length - 1);
    }

    private TreeNode sortedArrayToBSTHelper(int[] nums, int begin, int end) {
        if (begin > end) return null;
        if (begin == end) return new TreeNode(nums[begin]);
        int mid = (begin + end) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBSTHelper(nums, begin, mid - 1);
        root.right = sortedArrayToBSTHelper(nums, mid + 1, end);
        return root;
    }

    public boolean hasAlternatingBits(int n) {
        while (n != 0) {
            if ((n & 1) == ((n >>> 1) & 1)) return false;
            n >>>= 1;
        }
        return true;
    }

    public int smallestRangeI(int[] A, int K) {
        int min = A[0];
        int max = A[0];
        for (int i : A) {
            min = Math.min(min, i);
            max = Math.max(max, i);
        }
        int ans = max - min - 2 * K;
        return ans < 0 ? 0 : ans;
    }

    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length / 2; i++) {
            sum += nums[i * 2];
        }
        return sum;
    }

    List<Integer> preAns;

    public List<Integer> preorder(Node root) {
        preAns = new LinkedList<>();
        setPreAns(root);
        return preAns;
    }

    private void setPreAns(Node root) {
        if (root == null) return;
        preAns.add(root.val);
        for (Node child : root.children) {
            setPreAns(child);
        }
    }

    List<Integer> postAns;

    public List<Integer> postorder(Node root) {
        postAns = new LinkedList<>();
        setPostAns(root);
        return postAns;
    }

    private void setPostAns(Node root) {
        if (root == null) return;
        for (Node child : root.children) {
            setPostAns(child);
        }
        postAns.add(root.val);
    }

    public int[][] transpose(int[][] A) {
        int[][] ans = new int[A[0].length][A.length];
        for (int i = 0; i < A.length; i++) {
            for (int i1 = 0; i1 < A[0].length; i1++) {
                ans[i1][i] = A[i][i1];
            }
        }
        return ans;
    }

    public int addDigits(int num) {
        while (true) {
            int ans = digitsSum(num);
            if (ans < 10) {
                return ans;
            } else {
                num = ans;
            }

        }
    }

    public int digitsSum(int num) {
        int ans = 0;
        while (num != 0) {
            ans = ans + num % 10;
            num = num / 10;
        }
        return ans;
    }

    public int maxDepth(Node root) {
        if (root == null) return 0;
        int deep = 0;
        for (Node child : root.children) {
            deep = Math.max(deep, maxDepth(child));
        }
        return deep + 1;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        ListNode pB = headB;
        ListNode lA = null;
        ListNode lB = null;
        while (pA != null && pB != null) {
            if (pA == pB) return pA;
            if (pA.next == null && lA == null) lA = pA;
            if (pB.next == null && lB == null) lB = pB;
            if (lA != null && lB != null && lA != lB) return null;
            pA = pA.next;
            pB = pB.next;
            if (pA == null) pA = headB;
            if (pB == null) pB = headA;
        }
        return null;
    }

    public ListNode removeElements(ListNode head, int val) {
        ListNode h = new ListNode(-1);
        ListNode root = h;
        while (head != null) {
            if (head.val != val) {
                h.next = head;
                h = h.next;
            }
            head = head.next;
        }
        h.next = null;
        return root.next;
    }

    public int[] sortArrayByParityII(int[] A) {
        int i = 0, j = 1;
        while (i < A.length && j < A.length) {
            while (i < A.length && (A[i] & 1) == 0) i += 2;
            while (j < A.length && (A[j] & 1) == 1) j += 2;
            if (i < A.length) {
                swap(A, i, j);
            }
            i += 2;
            j += 2;
        }
        return A;
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


    public String reverseWords(String s) {
        if (s == null) return null;
        String[] strs = s.split(" ");
        StringBuilder ans = new StringBuilder();
        for (String str : strs) {
            ans.append(reverseString(str)).append(" ");
        }
        return ans.substring(0, ans.length() - 1);

    }

    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> list = new LinkedList<>();
        for (int i = left; i <= right; i++) {
            if (valid(i)) list.add(i);
        }
        return list;

    }

    private static boolean valid(int num) {
        int temp = num;
        while (temp != 0) {
            int cur = temp % 10;
            temp /= 10;
            if (cur == 0 || num % cur != 0) return false;
        }
        return true;
    }

    private static int[] decode = new int[256];

    public String[] findWords(String[] words) {
        String[] strs = {"qwertyuiopQWERTYUIOP", "asdfghjklASDFGHJKL", "zxcvbnmZXCVBNM"};
        for (int i = 0; i < strs.length; i++) {
            for (int i1 = 0; i1 < strs[i].length(); i1++) {
                decode[strs[i].charAt(i1)] = i;
            }
        }
        LinkedList<String> list = new LinkedList<>();
        for (String word : words) {
            if (isValid(word)) {
                list.add(word);
            }
        }
        String[] ans = new String[list.size()];
        return list.toArray(ans);
    }

    private static boolean isValid(String str) {
        int i = decode[str.charAt(0)];
        for (int i1 = 1; i1 < str.length(); i1++) {
            if (decode[str.charAt(i1)] != i) {
                return false;
            }
        }
        return true;
    }


    public String reverseVowels(String s) {
        char[] chars = s.toCharArray();
        int l = 0;
        int r = s.length() - 1;
        while (l < r) {
            while (l < r && !isVowels(chars[l])) {
                l++;
            }
            while (l < r && !isVowels(chars[r])) {
                r--;
            }
            if (l < r) {
                swap(chars, l++, r--);
            }
        }
        return new String(chars);
    }

    private boolean isVowels(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
                c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
    }

    private void swap(char[] chars, int l, int r) {
        if (chars[l] == chars[r]) return;
        char c = chars[l];
        chars[l] = chars[r];
        chars[r] = c;
    }

    public String reverseString(String s) {
        StringBuilder ans = new StringBuilder();
        for (int i = s.length() - 1; i >= 0; i--) {
            ans.append(s.charAt(i));
        }
        int a = 1;
        a = a + 1;
        a = a + 1;
        return ans.toString();
    }

    public int findComplement(int num) {
        int ans = 0;
        int flag = 0;
        while (num != 0) {
            if ((num & 1) == 0) {
                ans = ans | (1 << flag);
            }
            flag++;
            num >>>= 1;
        }
        return ans;
    }

    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode temp = root.right;
        root.right = invertTree(root.left);
        root.left = invertTree(temp);
        return root;
    }

    public boolean judgeCircle(String moves) {
        int x = 0;
        int y = 0;
        for (int i = 0; i < moves.length(); i++) {
            switch (moves.charAt(i)) {
                case 'U': {
                    y++;
                    break;
                }
                case 'D': {
                    y--;
                    break;
                }
                case 'R': {
                    x++;
                    break;
                }
                case 'L': {
                    x--;
                    break;
                }
            }
        }
        return x == 0 && y == 0;
    }

    private static boolean ans = false;

    public boolean isBalanced(TreeNode root) {
        ans = true;
        height(root);
        return ans;
    }

    private static int height(TreeNode root) {
        if (root == null) return 0;
        int l = height(root.left) + 1;
        int r = height(root.right) + 1;
        if (Math.abs(l - r) > 1) ans = false;
        return Math.max(l, r);
    }


    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left) + 1;
        int right = maxDepth(root.right) + 1;
        return Math.max(left, right);
    }

    public int missingNumber(int[] nums) {
        int sum = (nums.length + 1) * (nums.length) / 2;
        for (int num : nums) {
            sum -= num;
        }
        return sum;
    }

    public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        return res;
    }

    public int reverseBits(int n) {
        int res = 0;
        int count = 32;
        while (n != 0) {
            res <<= 1;
            if ((n & 1) == 1) {
                res += 1;
            }
            n >>>= 1;
            count--;
        }
        return res << count;
    }

    public int hammingWeight(int x) {
        int count = 0;
        while (x != 0) {
            if ((x & 1) == 1) {
                count++;
            }
            x >>>= 1;
        }
        return count;
    }

    public int hammingDistance(int x, int y) {
        int count = 0;
        while (x != 0 || y != 0) {
            if (((x & 1) == 1) != ((y & 1) == 1)) {
                count++;
            }
            x >>>= 1;
            y >>>= 1;
        }
        return count;
    }

    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        t1.val += t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }
}
